package sort;

import java.util.Iterator;

public class LinkList<T> implements Iterable<T> {
    //记录头节点
    private Node head;
    //记录链表的长度
    private int N;

    public LinkList() {

        //初始化头结点
        head = new Node(null, null);
        this.N = 0;
    }

    //清空链表
    public void clear() {
        head.next = null;
        head.item = null;
        N = 0;
    }

    //获取链表长度
    public int length() {
        return N;
    }

    //判断线性表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //获取指定位置i处的元素
    public T get(int i) {
        Node n = head.next;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return (T) n.item;
    }

    //向链表中添加元素
    public void insert(T t) {
        //找到最后一个节点，
        Node n = head;
        while (n.next != null) {
            n = n.next;
        }
        Node newNode = new Node(t, null);
        n.next = newNode;
        N++;
    }

    public void insert(int i, T t) {
        Node n = head;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        Node n0 = n;
        Node n1 = n0.next;
        Node newNode = new Node(t, n1);
        n0.next = newNode;
        N++;
    }

    //删除指定位置并返回删除的元素
    public T remove(int i) {
        Node n = head;
        for (int index = 0; index < i - 1; index++) {
            n = n.next;
        }
        Node n0 = n.next;
        Node n1 = n0.next;
        n.next = n1;
        N--;
        return (T) n0.item;
    }

    //查找第一次出现的位置，没有就返回-1
    public int indexOf(T t) {
        Node n = head;
        for (int i = 0; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }

    //链表反转
    public Node reverse(Node curr){
        //结束递归的部分
        if (curr.next==null){
            head.next=curr;
            return curr;

        }
        //返回值就是链表反转后当前结点的上一个结点
        Node pre=reverse(curr.next);
        //上一个结点的next域指向当前结点
        pre.next=curr;
        curr.next=curr;
        return curr;
    }

    @Override
    public Iterator iterator() {
        return new LIterator();
    }

    //接口不能直接创建对象，要创建个内部类再创建对象
    private class LIterator implements Iterator<T> {
        private Node n;

        public LIterator() {
            n = head;

        }

        @Override
        public boolean hasNext() {

            return n.next != null;
        }

        @Override
        public T next() {
            n = n.next;
            return (T) n.item;
        }
    }
}
